(1) Field of the Invention
This invention relates to an arrangement for encrypting digitized transmission data, and especially to an apparatus and method for such data encryption employed in pay broadcasting, secret communications, and the like.
(2) Related Arts
In accordance with the development of digital computers as well as their theory and integrated circuits, digital communication technology has been rapidly prevailing. With digital communication network open to the public, such problems as eavesdropping or forging by a third party are unavoidable. To cope with these problems, a sender generally transmits information by encrypting it in a certain process, while a receiver decrypts received information in the inverse of the encryption process. An example of such process proceeds as follows:
1) Binary digit data to be transmitted is divided into some blocks of data. PA1 2) Each block of data is encrypted. For example, it is exclusive-or(denoted by `+` or XOR)ed with predetermined binary digits called a secret key or a common key that is known only to the sender and the receiver, or it is permuted with other blocks of data according to a key. PA1 3) The data thus encrypted is sent via a public communication line. PA1 4) The receiver decrypts received data by applying the inverse execution. PA1 (a) At a first stage, the 64-bit input data is divided into two 32-bit blocks: INL (left) and INR (right). PA1 (b) The block of data INR is encrypted in an F-function unit, using an encryption Key 0. PA1 (c) The other block of data INL is XORed with the output F(INR) of the F-function unit. The result of XOR is (INL+F(INR)). PA1 (d) Each block of data in the above steps (b) and (c) is permuted with the other and transmitted to the next stage. PA1 (1) The relationship between the input and output of the F-function unit at each stage is so simple that the cryptanalysts can analyze the encryption easily. PA1 (2) Although the increase in the number of division of input data can diminish the hardware scale, it lessens the effects of encryption, so that the number of iteration to apply input data to the execution unit must be increased. PA1 (3) The increase in the number of iteration slows down the processing speed.
The following are the description of data encryption apparatuses with which this invention is closely concerned.
(A first conventional apparatus) PA0 (A second conventional apparatus)
There is a data encryption method called a involution system or iterated crypro algorithm, that is for secret communication or signed communication in open digital communication network. This is one method of the conventional crypro algorithm and is utilized both in Data Encryption Standard (DES) which is most popular encryption algorithm in the U.S., and in Fast data Encipherment ALgorithm (FEAL) later developed in Japan. DES and FEAL are detailed respectively in FIPS PUB 46, NBS Jan., 1977 and in "Fast Data Encipherment algorithm FEAL" by A. Shimizu & S. Miyaguchi, Advances in Cryptology-EUROCRYPT '87, Springer-Verlag.
FIG. 1 shows the configuration of an involution system for 64-bit input in general.
The involution system processes iterally the process as follows:
The reason of using an XOR operation in the step (c) is that thus combined data can include the blocks on both sides, and additionally the same XOR can be used in decryption.
Besides blocks of data to be encrypted, the other input of the F-function unit is a data which is just called a key or either "secret key" or "common key." The way of encryption in the F-function unit varies depending on the key. In FIG. 1, Key i is used at i-th stage (i=0, 1, 2- - - ), and a slash with "32" on a line indicates that the line is for 32 bits.
Generally, when the involution system is realized in hardware or software, a single execution unit for one stage provided with an F-function unit for data encryption and an XOR circuit is iteratively used. Therefore, hardware with the involution system can be compact, while software with the involution system can manage with a smaller program capacity.
Decryption can be performed by applying keys used in the encryption process in the inverse way and by applying the same hardware and programs. That is, the eventual results of data encryption, OUTL and OUTR become the input data INL and INR respectively, and the encryption process proceeds backwards using the keys in the reverse order like Key(L-1), - - - , Key 1, and Key 0 in the same F-function units until the initial input values are finally revealed.
As described hereinbefore, the involution system has excellent characteristics of capable of both encrypting and decrypting data to be transmitted only with an execution unit for just one stage, and further capable of making "strong" encryption by increasing the number of stages.
However, in 1990, Eli Biham and Adi Shamir at The Weizmann Institute of Science proposed a general attack to the involution system. This "attack" means that a third party (cryptanalyst) without knowledge of the key analogizes it based on information open to the public such as broadcasting, and then successfully cryptanalyzes the data transmitted. The attack is applicable to any involution system regardless of the F-function unit for data encryption and is called Differential Cryptanalysis. This can be realized when cryptanalysts can obtain the difference between the two outputs corresponding to two inputs having difference designated by the cryptanalysts (difference means XOR and is indicated by +). For example, when the cryptanalysts input Ti and Ti+.delta. (i=1, 2, 3 - - - and .delta. is the value of difference) to a data encrypter fK with a fixed secret key k, if he can get the fK(Ti)+fK(Ti+.delta.), then he can realized the attack. This is performed as follows: first, a plurality of output differences are collected by changing the values of Ti or the difference .delta., and then the effects caused by the algorithm is statistically analyzed that are given from the difference of a pair of input data to that of a pair of output data.
In order to make this differential cryptanalysis invalid, it is required to increase the number of stages in the involution system, and 16 times and 32 times are regarded the minimum numbers respectively in DES and in FEAL. Such attacks are detailed in "Differential Cryptanalysis of DES-Like Cryptosystems" by Eli Biham and Adi Shamir, Advances in Crypotology-CRYPTO'90, Springer-Verlag.
The basic strategy to make differential cryptanalysis invalid is to increase the number of times of iteration, which, however, demands more processing time as well as additional equipment.
In the meanwhile, the involution system itself involves the causes of making the differential cryptanalysis valid. In other words, the relationship between input data and output data of the F-function unit at each stage is comparatively simple. For example, in FIG. 1, the input of the F-function unit at the first stage is INR, that at the second stage is the XOR between INL and the output of the F-function unit of the first stage, and that at the third stage is the XOR between INR and the output of the F-function unit at the second stage. Hence, such characteristics of the involution system give cryptanalysts big clue when they can select input data as they like and know the output data.
The involution system allows input data to be divided into more than 2, so that the processing scale of the F-function unit can be diminished when the bit number of input data is the same. Accordingly, the hardware scale can be reduced. Such a challenge is described in U.S. Pat. No. 5,008,935 or "On the construction of block ciphers probably secure and not relying on any unproved hypotheses", by Y. Zheng, T. Matsumoto and H. Imai, Advances in Cryptology-CRYPTO'89, Springer-Verlag.
FIG. 2 is a revision of the construction shown in FIG. 3 of U.S. Pat. No. 5,008,935 with a general type F-function unit for data encryption. In the figure, 64-bit input data A is divided into four blocks of 16-bit data: A0, A1, A2, and A3. First, an F-function unit receives A0 and then the output F(A0) thereof is combined with the other three blocks of data by XOR. In the same manner, each of the second, third, fourth blocks of data is inputted to the F-function unit in turn so as to be combined with the other three blocks of data. In this process, four blocks of data are shifted to inputted to an F-function unit for encrypting 16-bit data. Decryption can be performed using the same hardware as encryption like in the first conventional apparatus. However, the order to use the keys must be reversed.
Although the involution system shown in FIG. 1 can encrypt the entire input data in two stages, at least four times of iteration must be performed in this construction. As a result, the effects of encryption at one stage is less than in the first conventional apparatus, so that the number of iteration must be increased for enough encryption. Additionally, Eli Biham says in the above-mentioned book that differential cryptanalysis is applicable to such extended involution system.
As described hereinbefore, the problems of the conventional data encryption apparatuses are as follows: